class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int>st;
        for (auto& str : tokens)
        {
            if (str == "+" || str == "-" || str == "*" || str == "/")
            {
                int right = st.top();
                st.pop();
                int left = st.top();
                st.pop();
                switch (str[0])
                {
                case '+':
                {st.push(left + right);
                break; }
                case '-':
                {st.push(left - right);
                break; }
                case '*':
                {st.push(left * right);
                break; }
                case '/':
                { st.push(left / right);
                break; }
                }
            }
            else
            {

                st.push(stoi(str));



            }














        }






        return st.top();








    }
}; class Solution {
public:
    bool isqueen(int row, int col, vector<string>& chessboard, int n)
    {
        for (int i = 0; i < row; i++)
        {
            if (chessboard[i][col] == 'Q')
                return false;
        }
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
        {
            if (chessboard[i][j] == 'Q')
                return  false;




        }
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
        {
            if (chessboard[i][j] == 'Q')
                return false;
        }



        return true;
    }
    vector<vector<string>> result;
    void backtracking(vector<string>& chessboard, int row, int n)
    {
        if (row == n)
        {
            result.push_back(chessboard);
            return;
        }
        for (int i = 0; i < n; i++)
        {
            if (isqueen(row, i, chessboard, n))
            {
                chessboard[row][i] = 'Q';
                backtracking(chessboard, row + 1, n);
                chessboard[row][i] = '.';
            }
            else
            {
                continue;
            }







        }









    }
    vector<vector<string>> solveNQueens(int n) {
        vector<string>chessboard(n, string(n, '.'));
        result.clear();
        backtracking(chessboard, 0, n);
        return result;

    }
}; class Solution {
public:
    bool isok(int row, int col, char k, vector<vector<char>>& board)
    {
        for (int i = 0; i < 9; i++)
        {
            if (board[i][col] == k)
                return false;




        }
        for (int i = 0; i < 9; i++)
        {
            if (board[row][i] == k)
                return false;




        }
        int startx = (row / 3) * 3;
        int starty = (col / 3) * 3;
        for (int i = startx; i < startx + 3; i++)
        {
            for (int j = starty; j < starty + 3; j++)
            {
                if (board[i][j] == k)
                    return false;




            }
        }
        return true;

    }




    bool backtracking(vector<vector<char>>& board)
    {
        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board[0].size(); j++)
            {
                if (board[i][j] == '.')
                {
                    for (char k = '1'; k <= '9'; k++)
                    {
                        if (isok(i, j, k, board))
                        {
                            board[i][j] = k;
                            int result = backtracking(board);
                            if (result)return true;
                            board[i][j] = '.';
                        }






                    }
                    return false;









                }





            }


        }

        return true;








    }





    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);















    }
}; class Solution {
public:
    int left, right = 0;
    string path;
    vector<string>result;
    int n;
    void  dfs()
    {
        if (right == n)
        {
            result.push_back(path);
            return;
        }


        if (left < n)
        {
            path.push_back('(');
            left++;
            dfs();
            left--;
            path.pop_back();
        }
        if (right < left)
        {
            path.push_back(')');
            right++;
            dfs();
            right--;
            path.pop_back();
        }









    }



    vector<string> generateParenthesis(int _n) {
        n = _n;
        dfs();
        return result;






    }
}; class Solution {
public:
    int sum = 0;
    int  path;
    void dfs(vector<int>& nums, int index)
    {
        sum += path;
        for (int i = index; i < nums.size(); i++)
        {
            path ^= nums[i];
            dfs(nums, i + 1);
            path ^= nums[i];



        }






    }
    int subsetXORSum(vector<int>& nums) {
        dfs(nums, 0);
        return sum;








    }
}; class Solution {
public:
    int sum = 0;
    bool used[16];
    void dfs(int pos, int n)
    {
        if (pos == n + 1)
        {
            sum++;
            return;
        }

        for (int i = 1; i <= n; i++)
        {
            if (!used[i] && (pos % i == 0 || i % pos == 0))
            {
                used[i] = true;
                dfs(pos + 1, n);
                used[i] = false;
            }





        }







    }
    int countArrangement(int n) {
        dfs(1, n);
        return sum;









    }
}; class Solution {
public:
    char change(char ch)
    {
        if (ch >= 'a' && ch <= 'z')
            return ch - 32;
        else
            return ch + 32;





    }
    vector<string> result;
    string path;
    void dfs(string& s, int pos)
    {
        if (s.size() == pos)
        {
            result.push_back(path);
            return;
        }
        path.push_back(s[pos]);
        dfs(s, pos + 1);
        path.pop_back();

        char ch = s[pos];
        if (ch < '0' || ch>'9')
        {
            char ret = change(ch);
            path.push_back(ret);
            dfs(s, pos + 1);
            path.pop_back();







        }







    }

    vector<string> letterCasePermutation(string s) {
        dfs(s, 0);
        return result;












    }
};